Content Addressable Memories (CAMs) are memories used to store and retrieve information based on comparison of a search key to contents of memory locations. Besides the means to fetch the input search key and means to deliver the output information about matched locations, each cell in a conventional CAM comprises a storage element to store and retrieve data and comparison circuitry to compare the search key data to the stored data. These conventional CAMs have been extensively used in routers for storing and retrieving Internet Protocol (IP) related information. However, the conventional CAMs require data to be stored in a particular order known as Table Management. Table management results in an additional burden in terms of time and resources on the router, as Table Management requires execution of time consuming tasks.
In Internet terminology, routing is the technique by which information finds its way from one networked computer to another. IPs are used to accomplish the task of routing by using IP addresses to communicate across any set of interconnected networks. These protocols are equally well suited for Local Area Network (LAN) and Wide Area Network (WAN) communications. There are several different addressing schemes that are being used on the Internet for IP address of a networked device. Most widely used IP version 4 (IPv4) addressing schemes use a 32-bit address and are known as IP version 4 (IPv4). The original IPv4 categorizes 32-bit addresses into three major classes of address structure, Classes A through C. In Class A addressing, the initial 8 bits represent the Network ID and the rest of 24 bits represent the Host ID. In Class B, 16 bits are used to represent the Network ID and rest represent the Host ID. In Class C 24 bits represent the Network-ID and 8 bits are used to define the Host ID. Using this addressing scheme, the Internet could support the following: 126 Class A networks that could include up to 16,777,214 hosts each along with 65,000 Class B networks that could include up to 65,534 hosts each, and over 2 million Class C networks that could include up to 254 hosts each.
While this addressing scheme has been tremendously popular, it has several drawbacks. Because Internet addresses were generally only assigned in three sizes, there were lots of wasted addresses. For example, if a company needs 100 IP addresses for its network, it would be assigned the Class closest to its requirement having smallest number of addresses (Class C), but that still meant 154 unused addresses, and if a company needed 300 addresses then it will be assigned a Class B address space, where out of 65536 addresses only 300 addresses would be used wasting 65236 addresses. This led to the near term exhaustion of Class B network address space. Another problem arose due to massive popularity and resultant growth of the Internet. As the Internet has grown, the number of networks on the Internet has increased rapidly and has resulted in the rapid growth in the size of the global Internet's routing table. Internet routers are fast approaching their limit on the number of routes they can support. Wasting of addresses and rapid growth along with the expandable nature of Internet throughout the world has led to concerns about exhaustion of Ipv4 addresses.
This concern has led to the development of a new scheme known as Classless Inter-Domain Routing (CIDR). This new scheme replaces the existing Classes with fixed bit length Network prefix with a variable length prefix. By accurately allocating only the amount of address space that was actually needed, the address space crisis could be avoided for many years. This was first proposed in 1992 as a scheme called Supernetting. Under supernetting, the classful subnet masks were extended so that a network address and subnet mask could, for example, specify multiple Class C subnets with one address. For example, If 1000 addresses are needed, 4 Class C networks are supernetted together:
192.60.128.0(11000000.00111100.10000000.00000000)Class Csubnetaddress192.60.129.0(11000000.00111100.10000001.00000000)Class Csubnetaddress192.60.130.0(11000000.00111100.10000010.00000000)Class Csubnetaddress192.60.131.0(11000000.00111100.10000011.00000000)Class Csubnetaddress192.60.128.0(11000000.00111100.10000000.00000000)Super-nettedSubnetaddress255.255.252.0(11111111.11111111.11111100.00000000)SubnetMask192.60.131.255(11000000.00111100.10000011.11111111)Broadcastaddress
In this example, the subnet 192.60.128.0 includes all the addresses from 192.60.128.0 to 192.60.131.255. As you can see in the binary representation of the subnet mask, the Network portion of the address is 22 bits long, and the host portion is 10 bits long. Under CIDR, the subnet mask notation is reduced to simplified shorthand. Instead of spelling out the bits of the subnet mask, it is simply listed as the number of 1s bits that start the mask. In the above example, instead of writing the address and subnet mask as 192.60.128.0, Subnet Mask 255.255.252.0, the network address would be written simply as: 192.60.128.0/22. This indicates the starting address of the network, and number of 1s bits (22) in the network portion of the address. This notation works in binary (11111111.11111111.11111100.00000000).
The use of a CIDR notated address is the same as for a Classful address. Classful addresses can easily be written in CIDR notation (Class A=/8, Class B=/16, and Class C=/24)
CIDR Block# EquivalentPrefixClass C# of Host Addresses/27⅛ th of a Class C 32 hosts/26¼ th of a Class C 64 hosts/25½ th of a Class C 128 hosts/241 Class C 256 hosts/232 Class C 512 hosts/224 Class C1024 hosts/218 Class C2048 hosts/2016 Class C 4096 hosts/1932 Class C 8192 hosts/1864 Class C 16,384 hosts  /17128 Class C 32,768 hosts  /16256 Class C 65,536 hosts  /15512 Class C 131,072 hosts  /141,024 Class C   262,144 hosts  /132,048 Class C   524,288 hosts  
Many CIDR implementation schemes used currently arrange the IP addresses in a CAM such that the IP addresses with the longest prefix are stored in the location closest to the last location of the CAM. This technique is often referred to as Table Management, and is used because the CAM provides an output corresponding to the first encountered match result while checking from last memory location. These schemes require the user to ensure that the CAM stores the IP address with highest prefix length at the lowest address of the CAM.
In these implementations, the CAM is divided into blocks of different sizes such that a block at the lowest address of the CAM is allocated for the IP addresses with the longest prefix and subsequent blocks for second longest prefix and so on as shown in FIG. 1. This requirement, of storing data in particular blocks, places a significant burden on the router in terms of allocation process. For instance, if an IP address is to be located in a block with no empty cell then an empty cell has to be created by increasing the size of that block by searching for an empty cell in the nearest blocks. Once an empty cell is found, to create an empty cell in the desired block, the top most element of the block with the empty cell has to be shifted to the empty cell, creating an empty cell at the top. Subsequent blocks then have to be resized to include the new empty cell, the process being repeated until an empty cell is created in the desired block to store IP address as shown in FIG. 2. This exercise is both cumbersome and time consuming and can sometimes result in resizing of the entire CAM.
U.S. Pat. No. 6,237,061 describes a method for finding longest prefix match, which requires Table Management. Further a U.S. Pat. No. 6,460,112 describes a method and device for CIDR without requiring table management and allowing CAM to be arbitrarily loaded with CIDR addresses into the CAM device. This patent requires two internal searches to be conducted, the location having success in these two searches is the one having a matching entry with longest prefix. First search is on data word to find longest prefix among the hit locations, second is on mask (prefix) word to find entries with that longest mask. Only one location will succeed in both searches and will drive ROM (Priority Encoder) word-line. In this patent, prefix logic circuits determine the longest prefix among the CAM locations that matches the search key, regardless of where the matching locations are located in the CAM array. Once prefix is known it then searches which location has that prefix through prefix match-lines. This patent has additional hardware than the conventional CAM array, as both data and mask bit have compare logic. Thus both have comparand bit-lines, match-lines and data lines. It also has a prefix-logic (2-input NAND gate) with each data and mask bit. Also operation can't be pipelined until the time both searches are completed for maximum throughput. Thus, the time for searching next CIDR address would require considerable amount of time.
A co-pending Indian application 1319/Del/2003 also describes a method and device for CIDR with zero table management. This invention provides a Content Addressable Memory (CAM) with an improved priority encoder enabling random storage of CIDR IP addresses in memory. This encoder uses a counter, which is incremented starting from the value of zero. At every increment, the value stored in the counter is simultaneously compared with the prefix of all match locations and the index of the match location is stored by overwriting the previous stored value associated with a lower counter value. As a result at the end of count, only one match location is left.
While this is certainly an improvement over the prior art, the approach still has some redundancies. While a simultaneous comparison is performed for all hit locations, the matched locations with lower prefix values than the stored value of the counter are not eliminated from the comparison process. The aforementioned drawback also results in unnecessary comparison after the longest prefix has been found as the process continues until the counter reaches it's maximum value. It is seen that the CAM takes 2N clock cycles, for a CAM with a N bit counter to count from 0 to 2N−1, and additional Read operation time to retrieve indices from a Read-Only Memory. Therefore, there is a need for more efficient CAMs, which result in faster searches for CIDR.